package datastructure.book.tujiesuanfa.find._1_all;

import datastructure.book.tujiesuanfa.list.bean.ListNode;

import java.util.HashMap;

public class Solution {
    /**
     * 寻找字符串中第一个只出现一次的字符
     * 例：
     * abbccdeff     第一个只出现一次的字符为：a
     * ccdd       没有只出现一次的字符返回空  ‘’
     */
    public char dismantlingAction(String arr) {
        if (arr == null || arr.isEmpty()) {
            return ' ';
        }
        char[] charArray = arr.toCharArray();
        int[] cnt = new int[charArray.length];
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < charArray.length; i++) {
            Integer charIndex = map.get(charArray[i]);
            if (charIndex == null) {
                cnt[i] = 1;
                map.put(charArray[i], i);
            } else {
                cnt[charIndex]++;
            }
        }
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] == 1) {
                return charArray[i];
            }
        }
        return ' ';
    }

    /**
     * 非严格递增整数数组 scores，请返回目标成绩 target 的出现次数。
     * 非严格递增，即相邻元素可能相等的递增
     * 例：1,2,3,3,4，4，5  其中 3出现2次
     * 数组中不存在target返回0
     */
    public int countTarget(int[] scores, int target) {
        if (scores == null || scores.length == 0) {
            return 0;
        }
        int i = 0;
        int j = scores.length-1;
        int cnt = 0;
        while (i <= j) {
            int mid = (i+j)/2;
            if (scores[mid] > target) {
                j = mid-1;
            } else if (scores[mid] < target) {
                i = mid+1;
            } else {
                cnt++;
                for (int m = mid-1; m >= 0 ; m--) {
                    if (scores[m] == target) {
                        cnt++;
                    } else {
                        break;
                    }
                }
                for (int n = mid+1; n < scores.length ; n++) {
                    if (scores[n] == target) {
                        cnt++;
                    } else {
                        break;
                    }
                }
                break;
            }
        }
        return cnt;
    }

    /**
     * 找到数组中缺少的自然数，仅缺少一个
     * 例：
     * [0,1,2,3,5]  缺少  4
     * [0,1,3,4,5]  缺少  2
     */
    public int takeAttendance(int[] records) {
        if (records == null || records.length == 0) {
            return -1;
        }
        if (records.length == 1) {
            return 1;
        }
        int i = 0;
        int j = records.length-1;
        while (i < j) {
            int mid = (i+j)/2;
            if (records[mid] == mid) {
                i = mid + 1;
            } else {
                j = mid - 1;
                if (j >= 0) {
                    if (records[j] == j) {
                        j++;
                        break;
                    }
                } else {
                    j++;
                    break;
                }
            }
        }
        if (records[j] != j) {
            return records[j] - 1;
        } else {
            return j+1;
        }
    }

    /**
     * 二维数组，每行递增，每列递增，查找是否有目标数
     * 例：是否有8，返回true
     * 1, 4, 7, 11,15
     * 2, 4, 8, 12,19
     * 3, 5, 9, 16,22
     * 10,11,14,17,24
     * 18,19,23,26,30
     */
    public boolean findTargetIn2DPlants(int[][] plants, int target) {
        if (plants == null || plants.length == 0 || plants[0].length == 0) {
            return false;
        }
        for (int[] plant : plants) {
            if (plant[0] > target) {
                return false;
            }
            if (plant[plant.length - 1] < target) {
                continue;
            }
            int l = 0;
            int r = plant.length - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (plant[mid] == target) {
                    return true;
                } else if (plant[mid] < target) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return false;
    }

    /**
     * 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。
     * 例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
     * 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
     * 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
     * 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
     * 给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。
     * 请你找出并返回数组中的 最小元素 。
     */
    public int inventoryManagement(int[] stock) {
        if (stock == null || stock.length == 0) {
            return 0;
        }
        for (int i = 0; i < stock.length-1; i++) {
            if (stock[i + 1] < stock[i]) {
                return stock[i+1];
            }
        }
        return stock[0];
    }
}
